package day_7_8;

public class Main3 {
    /**
     * 41. 缺失的第一个正数
     * https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
     */
    public int firstMissingPositive(int[] nums) {
        // 进行替换操作
        // 进行检查 i 是否等于 nums[i] 的值。
        // 如果相等，那么说明当前位置就是正常的，如果不等，，那么就是将nums[i]的值和这个值对应的下标位置的nums值进行交换
        // 如果这个位置的值是小于1的，那么就不需要进行处理
        // 但是可能会出现重复的数值，如果对于这个重复的值进行多次处理就会进入死循环，所以需要知道当前的值是否已经处理过了
        // 也就是这个值对应的下标下对应的nums值是否是和这个值相等的，相等就是处理过，就不处理了，如果不等就进行处理
        // i 是否等于 nums[i] =》 nums[i] 是否等于 nums[nums[i]]
        // 注意：上述的下标推测是从1 开始，那么这个是从0 开始，所以需要进行处理
        int n = nums.length;
        for(int i = 0;i < n;i++) {
            while(1 <= nums[i] && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                int j = nums[i] - 1;
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        // 再次遍历从头到尾第一个不符合下标和对应值不相等的就是第一个正数
        for(int i = 0;i < n;i++) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 遍历结束，说明缺少最后一个位置的值
        return n + 1;
    }
}
